/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/paint-house-ii
   @Language: C++
   @Datetime: 19-06-03 16:57
   */

class Solution {
public:
	/**
	 * @param costs: n x k cost matrix
	 * @return: an integer, the minimum cost to paint all houses
	 */
	int minCostII(vector<vector<int> > &costs) {
		// write your code here
		if(costs.size()==0) return 0;
		vector<int> colors=costs[0];
		for(int i=1; i<costs.size(); ++i){
			int min1=INT_MAX, min2=INT_MAX, min1id;
			for(int j=colors.size(); j--;){
				if(colors[j]<min1){
					min1=colors[j];
					min1id=j;
				}
			}
			for(int j=colors.size(); j--;)
				if(j!=min1id) min2=min(min2,colors[j]);
			for(int j=colors.size(); j--;)
				colors[j]=costs[i][j]+(j==min1id?min2:min1);
		}
		int res=colors[0];
		for(int i=1; i<colors.size(); ++i)
			res=min(res,colors[i]);
		return res;
	}
};
